package _2022.hot100._300_最长递增子序列;



/**
 * @author： YHSimon
 * @date： 2022-05-25 10:33
 */
public class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;
        int ans = 1, len = nums.length;
        int[] dp = new int[len];
        dp[0]=1;
        for (int i = 1; i < len; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }

    public int lenghtOfLIS2(int[] nums){
        int len=1,n=nums.length;
        if(n==0) return 0;
        int[] d=new int[n+1];
        d[len]=nums[0];
        for(int i=1;i<n;i++){
            if(nums[i]>d[len]){
                d[++len]=nums[i];
            }else{
                int l=1,r=len,pos=0;//若找不到说明所有的数都比nums[i]大，此时要更新新dp[1]，所以这里将pos=0;
                while(l<=r){
                    int mid=(l+r)/2;
                    if(d[mid]<nums[i]){
                        pos=mid;
                        l=mid+1;
                    }else{
                        r=mid-1;
                    }
                }
                d[pos+1]=nums[i];
            }
        }
        return len;
    }
}
